import ArrayQueue from "./01_实现队列结构";

// 约瑟夫环问题: 有n个人围成一圈，从第一个人开始报数，每数到m时，该人出列，直到所有人都出列为止，求最后剩下的数字
// 定义一个函数，用于计算最后剩下的数字
function lastRemainning(total: number, num: number) {
  // 创建一个队列，用于存储数字
  const queue = new ArrayQueue<number>();

  // 从数字0开始, 注意
  for (let i = 0; i < total; i++) {
    // 将数字加入队列
    queue.enqueue(i);
  }

  // 当队列中只剩下一个数字时，停止循环
  while (queue.size() > 1) {
    // 将队列中的前num-1个数字依次移到队列末尾
    for (let i = 1; i < num; i++) {
      queue.enqueue(queue.dequeue()!);
    }
    // 将队列中的第一个数字移除
    queue.dequeue();
  }

  // 返回队列中剩下的数字
  return queue.dequeue();
}

console.log(lastRemainning(5, 3));
console.log(lastRemainning(10, 17));
